package _430_Flatten_a_Multilevel_Doubly_Linked_List;

import java.util.Stack;

/**
 * Created by 孙加辉 on 2018/7/22.
 */
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;

    public Node() {}

    public Node(int _val,Node _prev,Node _next,Node _child) {
        val = _val;
        prev = _prev;
        next = _next;
        child = _child;
    }
}
class Solution{
    public Node flatten(Node head) {
        if(head==null)
            return null;
        Node res = new Node();
        Node p = new Node();
        res.next = p;
        p.prev = res;
        Stack<Node> stack = new Stack<Node>();
        stack.push(head);
        while(!stack.isEmpty()){
            Node temp = stack.pop();
            if(temp.next!=null)
                stack.push(temp.next);
            if(temp.child!=null)
                stack.push(temp.child);
            p.next = temp;
            temp.prev = p;
            temp.child = null;
            p = temp;
            //System.out.println(temp.val);
        }
        res.next.next.prev = null;
        return res.next.next;
    }
}
public class _430_Flatten_a_Multilevel_Doubly_Linked_List {
    public static void main(String[] args){
        Node a1 = new Node();
        Node a2 = new Node();
        Node a3 = new Node();
        Node a4 = new Node();
        Node a5 = new Node();
        Node a6 = new Node();
        Node a7 = new Node();
        Node a8 = new Node();
        Node a9 = new Node();
        Node a10 = new Node();
        Node a11 = new Node();
        Node a12 = new Node();
        a1.val = 1;
        a2.val = 2;
        a3.val = 3;
        a4.val = 4;
        a5.val = 5;
        a6.val = 6;
        a7.val = 7;
        a8.val = 8;
        a9.val = 9;
        a10.val = 10;
        a11.val = 11;
        a12.val = 12;

        a1.next = a2;
        a2.next = a3;
        a3.next = a4;
        a3.child = a7;
        a4.next = a5;
        a5.next = a6;
        a7.next = a8;
        a8.next = a9;
        a8.child = a11;
        a9.next = a10;
        a11.next = a12;


        Solution solution = new Solution();
        Node aa = solution.flatten(null);
        while(aa.next!=null){
            aa = aa.next;
        }
        while (aa!=null){
            System.out.println(aa.val);
            aa = aa.prev;
        }
    }
}
